240. 搜索二维矩阵 II

为保证权益，题目请参考 240. 搜索二维矩阵 II(From LeetCode).

解决方案1

CPP

//
// Created by lenovo on 2020-09-18.
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    bool search(vector<vector<int>> &matrix, int target, int t, int b, int l, int r) {
        if (t > b || l > r) {
            return false;
        }

        int rm = (t + b) / 2;
        int cm = (l + r) / 2;
        if (matrix[rm][cm] == target) {
            return true;
        } else if (matrix[rm][cm] > target) {
            return search(matrix, target, t, rm, l, cm);
        } else {
            return search(matrix, target, t, rm, cm, r)
                   || search(matrix, target, rm, b, l, cm)
                   || search(matrix, target, rm, b, cm, r);
        }
    }

public:
    bool searchMatrix(vector<vector<int>> &matrix, int target) {
        if(matrix.size() == 0){
            return false;
        }
        return this->search(matrix, target, 0, matrix.size(), 0, matrix[0].size());
    }
};

int main() {
    return 0;
}

Python

# 240. 搜索二维矩阵 II
# https://leetcode-cn.com/problems/search-a-2d-matrix-ii/


################################################################################
from typing import List


class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        x = 0
        y = len(matrix[0]) - 1

        while all([x < len(matrix), y >= 0]):
            if matrix[x][y] == target:
                return True
            elif matrix[x][y] < target:
                x += 1
            else:
                y -= 1
        
        return False


################################################################################

if __name__ == "__main__":
    solution = Solution()